package top.humbleyuan.double_pointer;

import top.humbleyuan.datastructure.linkedlist.LinkNode;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:06
 * @Des 删除排序链表重复元素
 */
public class LeetCode_82 {
    public static void main(String[] args) {
        // 一般解法
        m1();

        // 快慢指针
        m2();
    }

    public static void m1(){
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3,3,4,4,5,6,7,7,8,9 };
        head = LinkNode.formLink(head,vals);

        boolean flag = false;

        LinkNode root = new LinkNode(0);
        root.next = head;

        int preVal = head.val ;
        LinkNode temp = head.next;
        LinkNode preLink = root;

        while (temp != null) {
            if(temp.val == preVal) {
                flag = true;
                if(temp.next == null) {
                    preLink.next = null;
                    break;
                }
            }
            else {
                if(flag) {
                    preLink.next = temp;
                    flag = false;
                }
                else {

                    preLink = preLink.next;
                }
                preVal = temp.val;
            }
            temp = temp.next;
        }

        LinkNode.headToString(root.next);
    }

    public static void m2() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3,3,4,4,5};
        head = LinkNode.formLink(head,vals);

        LinkNode root = new LinkNode(0);
        root.next = head;

        //快慢指针
        //前一个和后一个比
        LinkNode slow = root;
        LinkNode fast = head;

        while (fast != null) {
            if(fast.next == null) {
                if(slow.next != fast)
                    slow.next = null;
                break;
            }

            if(fast.val != fast.next.val) {

                //前面有多个重复指针
                if(slow.next != fast) {
                    slow.next = fast.next;
                }else {
                    slow = fast;
                }
            }

            fast = fast.next;
        }
        LinkNode.headToString(root.next);
    }
}
